/*
 * sort.cpp
 *
 *  Created on: Mar 1, 2014
 *      Author: tony
 */

template<class T>
int indexOfSmallest(const T a[], int startIndex, int numberUsed);

template<class T>
void sort(T a[], int numberUsed) {
    int indexOfNextSmallest;
    for (int index = 0; index < numberUsed - 1; index++) {
    	//Place the correct value in a[index]:
         indexOfNextSmallest =
              indexOfSmallest(a, index, numberUsed);
         swapValues(a[index], a[indexOfNextSmallest]);
      //a[0] <= a[1] <=...<= a[index] are the smallest of the original array
      //elements. The rest of the elements are in the remaining positions.
    }
}

/**
 * Precondition: 0 <= startIndex < numberUsed. Array elements have values.
 *   The assignment and < operator work for values of type T.
 * Returns the index i such that a[i] is the smallest of the values
 *   a[startIndex], a[startIndex + 1],..., a[numberUsed - 1].
 */
template<class T>
int indexOfSmallest(const T a[], int startIndex, int numberUsed){
    T min = a[startIndex];
    int indexOfMin = startIndex;

    for (int index = startIndex + 1; index < numberUsed; index++)
        if (a[index] < min) {
            min = a[index];
            indexOfMin = index;
            //min is the smallest of a[startIndex] through a[index]
        }
    return indexOfMin;
}

